import java.util.*;

public class Leetcode {
}

//leetcode:1027:最长等差数列
class Solution1 {
    public int longestArithSeqLength(int[] nums) {
        //利用哈希表进行优化，但是这里的优化是每找一次才将这个数的值放入其中
        Map<Integer,Integer> hash = new HashMap<>();
        hash.put(nums[0],0);

        //初始化，将所有的值都设为2
        int n = nums.length;
        int[][] dp = new int[n][n];
        for(int i = 0; i < n; i++){
            Arrays.fill(dp[i],2);
        }

        int ret = 2;
        for(int i = 1; i < n;i++){//固定倒数第二个数
            //移动最后一个数，来找第一个数
            for(int j = i+1; j < n; j++){//枚举最后一个数
                int a = 2*nums[i] - nums[j];
                if(hash.containsKey(a)){
                    dp[i][j] = dp[hash.get(a)][i] + 1;
                }
                ret = Math.max(ret,dp[i][j]);
            }
            hash.put(nums[i],i);
        }
        return ret;
    }
}

//leetcode:446:等差数列划分
class Solution2 {
    public int numberOfArithmeticSlices(int[] nums) {
        //将数据对应的下标放入哈希表中
        Map<Long,List<Integer>> hash = new HashMap<>();
        int n = nums.length;
        for(int i = 0; i < n; i++){
            long tmp =(long)nums[i];
            //因为同一个值可能有多个，但是位置下标却不相同
            if(!hash.containsKey(tmp)){
                //因此我们可以创建一个链表来存储同一个值的不同下标
                hash.put(tmp,new ArrayList<Integer>());
            }
            hash.get(tmp).add(i);
        }

        int[][] dp = new int[n][n];
        int sum = 0;
        for(int j = 2; j < n; j++){//固定最后一个位置
            for(int i = 1; i < j; i++){//枚举倒数第二个位置
                long a = 2L*nums[i] - nums[j];//计算出前一个位置
                if(hash.containsKey(a)){//判断是否存在
                    for(int k : hash.get(a)){//存在枚举这个数的所有对应下标
                        if(k < i) dp[i][j] += dp[k][i] + 1;//如果这个数的下标是小于倒数第二个数的位置的，就就计算子序列的个数
                        else break;//如果大于就退出：优化
                    }
                }
                sum += dp[i][j];//得到所有位置的子序列个数
            }
        }
        return sum;
    }
}